#define _CRT_SECURE_NO_WARNINGS 1
//#include<stdio.h>
//#include<string.h>
//typedef struct zifu
//{
//    char ch[81];
//}Z;
//int main()
//{
//    int i, j;
//    Z z[5];
//    Z temp;
//    for (i = 0; i < 5; i++)
//    {
//        scanf("%s ", z[i].ch);
//    }
//    for (i = 1; i < 5; i++)
//    {
//        for (j = 0; j < 5 - i; j++)
//        {
//            if (strcmp(z[j].ch, z[j + 1].ch) > 0)
//            {
//                temp = z[j + 1];
//                z[j + 1] = z[j];
//                z[j] = temp;
//            }
//        }
//    }
//    printf("After sorted:\n");
//    for (i = 0; i < 5; i++)
//    {
//        printf("%s\n", z[i].ch);
//    }
//    return 0;
//}

//#include<stdio.h>
//typedef struct item
//{
//    int a;
//    int b;
//}ITEM;
//int main()
//{
//    int n;
//    while (scanf("%d", &n) != EOF)
//    {
//        ITEM a[n];
//        ITEM temp;
//        int i, j;
//        for (i = 0; i < n; i++)
//        {
//            scanf("%d", &a[i].a);
//        }
//        for (i = 0; i < n; i++)
//        {
//            scanf("%d", &a[i].b);
//        }
//        for (i = 1; i < n; i++)
//        {
//            for (j = 0; j < n - i; j++)
//            {
//                if (a[j].a > a[j + 1].a)
//                {
//                    temp = a[j + 1];
//                    a[j + 1] = a[j];
//                    a[j] = temp;
//                }
//                else if (a[j].a == a[j + 1].a && a[j].b < a[j + 1].b)
//                {
//                    temp = a[j + 1];
//                    a[j + 1] = a[j];
//                    a[j] = temp;
//                }
//            }
//        }
//        printf("result:\n");
//        for (i = 0; i < n; i++)
//        {
//            printf("%d %d\n", a[i].a, a[i].b);
//        }
//    }
//    return 0;
//}


//#include<stdio.h>
//int main()
//{
//    int n, m;
//    scanf("%d", &n);
//    int i, j;
//    int a[n];
//    for (i = 0; i < n; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    scanf("%d", &m);
//    int b[m];
//    for (i = 0; i < m; i++)
//    {
//        scanf("%d", &b[i]);
//    }
//    int c[n];
//    int flag = 1;
//    int count = 0;
//    for (i = 0; i < n; i++)
//    {
//        for (j = 0; j < m; j++)
//        {
//            if (a[i] == b[j])
//            {
//                flag = 0;
//                break;
//            }
//        }
//        if (flag == 1)
//        {
//            c[count++] = a[i];
//        }
//        flag = 1;
//    }
//    flag = 1;
//    for (i = 0; i < m; i++)
//    {
//        for (j = 0; j < n; j++)
//        {
//            if (b[i] == a[j])
//            {
//                flag = 0;
//                break;
//            }
//        }
//        if (flag == 1)
//        {
//            c[count++] = b[i];
//        }
//        flag = 1;
//    }
//    flag = 1;
//    int d[n];
//    int k = 0;
//    for (i = 0; i < count; i++)
//    {
//        for (j = 0; j < k; j++)
//        {
//            if (c[i] == d[j])
//            {
//                flag = 0;
//                break;
//            }
//        }
//        if (flag == 1)
//        {
//            d[k++] = c[i];
//        }
//        flag = 1;
//    }
//    for (i = 0; i < k; i++)
//    {
//        if (i == 0)
//        {
//            printf("%d", d[i]);
//        }
//        else
//        {
//            printf(" %d", d[i]);
//        }
//    }
//    return 0;
//}

//#include<stdio.h>
//int main()
//{
//    int n, k;
//    scanf("%d %d", &n, &k);
//    int a[k];
//    int count = 0;
//    int sum = 0;
//    int i, j;
//    int flag = 0;
//    for (i = n; i > 1; i--)
//    {
//        for (j = 2; j < i; j++)
//        {
//            if (i % j == 0)
//            {
//                flag = 1;
//                break;
//            }
//        }
//        if (flag == 0)
//        {
//            a[count++] = i;
//            sum += i;
//        }
//        if (count == k)
//        {
//            break;
//        }
//        flag = 0;
//    }
//    for (i = 0; i < count; i++)
//    {
//        printf("%d", a[i]);
//        if (i != count - 1)
//        {
//            printf("+");
//        }
//    }
//    printf("=%d", sum);
//    return 0;
//}


//#include<stdio.h>
//#include<string.h>
//typedef struct student
//{
//    char num[13];
//    char name[21];
//    int a;
//    int b;
//    int c;
//}STU;
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    getchar();
//    STU s[n];
//    int i;
//    char ch[30];
//    int flag = 1;
//    for (i = 0; i < n; i++)
//    {
//        scanf("%s%s%d%d%d", s[i].num, s[i].name, &s[i].a, &s[i].b, &s[i].c);
//    }
//    getchar();
//    scanf("%s", ch);
//    for (i = 0; i < n; i++)
//    {
//        if (strcmp(ch, s[i].name) == 0)
//        {
//            flag = 0;
//            printf("%s %s %d %d %d\n", s[i].num, s[i].name, s[i].a, s[i].b, s[i].c);
//        }
//    }
//    if (flag == 1)
//    {
//        printf("Not Found");
//    }
//    return 0;
//}


//#include<stdio.h>
//int main()
//{
//    int n, k;
//    scanf("%d %d", &n, &k);
//    int a[n];
//    int i, j;
//    int count = 0;
//    int temp;
//    for (i = 0; i < n; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    for (i = 1; i < n; i++)
//    {
//        if (k == count)
//        {
//            break;
//        }
//        for (j = 0; j < n - i; j++)
//        {
//            if (a[j] > a[j + 1])
//            {
//                temp = a[j + 1];
//                a[j + 1] = a[j];
//                a[j] = temp;
//            }
//        }
//        count++;
//    }
//    for (i = 0; i < n; i++)
//    {
//        if (i == 0)
//        {
//            printf("%d", a[i]);
//        }
//        else
//        {
//            printf(" %d", a[i]);
//        }
//    }
//    return 0;
//}

//#include<stdio.h>
//int main()
//{
//    int n;
//    int i, j, k;
//    scanf("%d", &n);
//    int count = 0;
//    for (i = 1; i < 30; i++)
//    {
//        for (j = 1; j < 75; j++)
//        {
//            for (k = 1; k < 150; k++)
//            {
//                if ((5 * i + 2 * j + k) == 150 && i + j + k == 100)
//                {
//                    if (count < n)
//                    {
//                        printf("%d %d %d\n", i, j, k);
//                        count++;
//                    }
//                }
//            }
//        }
//    }
//    return 0;
//}

//#include<stdio.h>
//#include<string.h>
//typedef struct ch
//{
//    char a[81];
//}CH;
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    getchar();
//    CH c[n];
//    int i, j;
//    for (i = 0; i < n; i++)
//    {
//        scanf("%s", c[i].a);
//    }
//    for (i = 1; i < n; i++)
//    {
//        for (j = 0; j < n - i; j++)
//        {
//            if (strcmp(c[j].a, c[j + 1].a) > 0)
//            {
//                CH temp;
//                temp = c[j + 1];
//                c[j + 1] = c[j];
//                c[j] = temp;
//            }
//        }
//    }
//    printf("Min is: %s", c[0].a);
//    return 0;
//}


//#include<stdio.h>
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int a[n][n];
//    int i, j;
//    int flag = 0;
//    for (i = 0; i < n; i++)
//    {
//        for (j = 0; j < n; j++)
//        {
//            scanf("%d", &a[i][j]);
//        }
//    }
//    for (i = 0; i < n; i++)
//    {
//        for (j = 0; j < n; j++)
//        {
//            if (a[j][i] != a[i][j])
//            {
//                flag = 1;
//            }
//        }
//    }
//    if (flag == 0)
//    {
//        printf("Yes");
//    }
//    else
//    {
//        printf("No");
//    }
//    return 0;
//}

//#include<stdio.h>
//typedef struct student
//{
//    char num[6];
//    char name[11];
//    int a;
//    int b;
//    int c;
//    int sum;
//}STU;
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    getchar();
//    STU s[n];
//    int i;
//    for (i = 0; i < n; i++)
//    {
//        scanf("%s %s %d %d %d", s[i].num, s[i].name, &s[i].a, &s[i].b, &s[i].c);
//        getchar();
//        s[i].sum = s[i].a + s[i].b + s[i].c;
//    }
//    int max = s[0].sum;
//    int k = 0;
//    for (i = 1; i < n; i++)
//    {
//        if (s[i].sum > max)
//        {
//            max = s[i].sum;
//            k = i;
//        }
//    }
//    printf("%s %s %d", s[k].name, s[k].num, s[k].sum);
//    return 0;
//}

//#include<stdio.h>
//int main()
//{
//    int n;
//    int flag = 0;
//    scanf("%d", &n);
//    int a[n];
//    int i, j;
//    for (i = 0; i < n; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    int b[n];
//    int count = 0;
//    for (i = 0; i < n; i++)
//    {
//        for (j = 0; j < count; j++)
//        {
//            if (a[i] == b[j])
//            {
//                flag = 1;
//                break;
//            }
//        }
//        if (flag == 0)
//        {
//            b[count++] = a[i];
//        }
//        flag = 0;
//    }
//    int c[count];
//    for (i = 0; i < count; i++)
//    {
//        c[i] = 0;
//    }
//    for (i = 0; i < count; i++)
//    {
//        for (j = 0; j < n; j++)
//        {
//            if (b[i] == a[j])
//            {
//                c[i]++;
//            }
//        }
//    }
//    int max = c[0];
//    int k;
//    for (i = 1; i < count; i++)
//    {
//        if (c[i] > max)
//        {
//            max = c[i];
//            k = i;
//        }
//    }
//    printf("%d %d", b[k], c[k]);
//    return 0;
//}